#include <bits/stdc++.h>
using namespace std;

/*
120. 三角形最小路径和
已解答
中等
相关标签
premium lock icon
相关企业
给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

 

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
示例 2：

输入：triangle = [[-10]]
输出：-10
 

提示：

1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-104 <= triangle[i][j] <= 104
 

进阶：

你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？
*/

// 法一
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        // 三角形null 路径和0
        if (triangle.empty())   return 0;
        // 行数
        int n = triangle.size();
        // init dp  用最后一行的元素作为初始状态（最后一行的最小路径就是自身）
        vector<int> dp = triangle.back();

        // 倒数第二行开始递推
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                // 最小路径和 = 当前node + 下一行的相邻的两个最小路径和
                dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]);
            }
        }
        // 结束之后 如果是回溯就要调用了 但是这里直接从top -- > bottom
        return dp[0];
    }
};